package ArrayTest;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr={5,7,3,1,6,9,4,2,8,0};
        int[] finalArray=mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(finalArray));

    }
    public static int[] mergeSort(int[] arr,int start,int end){
        //防止死循环
        if (start==end){
            return new int[] {arr[start]};
        }
        //拆分
        int mid=start+(end-start)/2;
        int [] leftArray=mergeSort(arr,start,mid);
        int [] rightArray=mergeSort(arr,mid+1,end);
        //合并
        int [] newArray=new int[leftArray.length+rightArray.length];
        int l=0,r=0,n=0;
        while (l<leftArray.length&&r<rightArray.length){
            newArray[n++]=leftArray[l]<=rightArray[r]?leftArray[l++]:rightArray[r++];
        }
        while (l<leftArray.length){
            newArray[n++]=leftArray[l++];
        }
        while (r<rightArray.length){
            newArray[n++]=rightArray[r++];
        }
        return newArray;
    }
}
